home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 6 / QRZ Ham Radio Callsign Database - Volume 6.iso / pc / files / amiga / rhinosrc.lha / slhc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-19  |  14.5 KB  |  587 lines
  1. /*
  2.  * Routines to compress and uncompress tcp packets (for transmission
  3.  * over low speed serial lines).
  4.  *
  5.  * Copyright (c) 1989 Regents of the University of California.
  6.  * All rights reserved.
  7.  *
  8.  * Redistribution and use in source and binary forms are permitted
  9.  * provided that the above copyright notice and this paragraph are
  10.  * duplicated in all such forms and that any documentation,
  11.  * advertising materials, and other materials related to such
  12.  * distribution and use acknowledge that the software was developed
  13.  * by the University of California, Berkeley.  The name of the
  14.  * University may not be used to endorse or promote products derived
  15.  * from this software without specific prior written permission.
  16.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  17.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  18.  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  19.  *
  20.  *    Van Jacobson (van@helios.ee.lbl.gov), Dec 31, 1989:
  21.  *    - Initial distribution.
  22.  *
  23.  *
  24.  * modified for KA9Q Internet Software Package by
  25.  * Katie Stevens (dkstevens@ucdavis.edu)
  26.  * University of California, Davis
  27.  * Computing Services
  28.  *    - 01-31-90    initial adaptation (from 1.19)
  29.  *    PPP.05    02-15-90 [ks]
  30.  *    PPP.08    05-02-90 [ks]    use PPP protocol field to signal compression
  31.  *    PPP.15    09-90     [ks]    improve mbuf handling
  32.  *    PPP.16    11-02     [karn]    substantially rewritten to use NOS facilities
  33.  *
  34.  *    - Feb 1991    Bill_Simpson@um.cc.umich.edu
  35.  *            variable number of conversation slots
  36.  *            allow zero or one slots
  37.  *            separate routines
  38.  *            status display
  39.  */
  40.  
  41. /*#include <mem.h>*/
  42. #include "global.h"
  43. #include "mbuf.h"
  44. #include "internet.h"
  45. #include "ip.h"
  46. #include "tcp.h"
  47. #include "slhc.h"
  48.  
  49. static char *encode __ARGS((char *cp,int16 n));
  50. static long decode __ARGS((struct mbuf **bpp));
  51.  
  52. /* if not a function, it is a macro that assumes alignment.
  53.  * Replace it with an unaligned version.
  54.  */
  55. #if defined(put16) && !defined(MSDOS) && !defined(LITTLE_ENDIAN)
  56. #undef put16
  57. #define put16(ptr,val)    (((char*)ptr)[0] = (val)>>8, ((char*)ptr)[1] = (val), (char*)ptr+2)
  58. #endif
  59.  
  60. /* Initialize compression data structure
  61.  *    slots must be in range 0 to 255 (zero meaning no compression)
  62.  */
  63. struct slcompress *
  64. slhc_init( rslots, tslots )
  65. int rslots;
  66. int tslots;
  67. {
  68.     register int16 i;
  69.     register struct cstate *ts;
  70.     struct slcompress *comp;
  71.  
  72.     comp = callocw( 1, sizeof(struct slcompress) );
  73.  
  74.     if ( rslots > 0  &&  rslots < 256 ) {
  75.         comp->rstate = callocw( rslots, sizeof(struct cstate) );
  76.         comp->rslot_limit = rslots - 1;
  77.     }
  78.  
  79.     if ( tslots > 0  &&  tslots < 256 ) {
  80.         comp->tstate = callocw( tslots, sizeof(struct cstate) );
  81.         comp->tslot_limit = tslots - 1;
  82.     }
  83.  
  84.     comp->xmit_oldest = 0;
  85.     comp->xmit_current = 255;
  86.     comp->recv_current = 255;
  87.  
  88.     if ( tslots > 0 ) {
  89.         ts = comp->tstate;
  90.         for(i = comp->tslot_limit; i > 0; --i){
  91.             ts[i].this = i;
  92.             ts[i].next = &(ts[i - 1]);
  93.         }
  94.         ts[0].next = &(ts[comp->tslot_limit]);
  95.         ts[0].this = 0;
  96.     }
  97.     return comp;
  98. }
  99.  
  100.  
  101. /* Free a compression data structure */
  102. void
  103. slhc_free(comp)
  104. struct slcompress *comp;
  105. {
  106.     if ( comp == NULLSLCOMPR )
  107.         return;
  108.  
  109.     if ( comp->rstate != NULLSLSTATE )
  110.         free( comp->rstate );
  111.  
  112.     if ( comp->tstate != NULLSLSTATE )
  113.         free( comp->tstate );
  114.  
  115.     free( comp );
  116. }
  117.  
  118.  
  119. /* Encode a number */
  120. static char *
  121. encode(cp,n)
  122. register char *cp;
  123. int16 n;
  124. {
  125.     if(n >= 256 || n == 0){
  126.         *cp++ = 0;
  127.         cp = put16(cp,n);
  128.     } else {
  129.         *cp++ = n;
  130.     }
  131.     return cp;
  132. }
  133.  
  134. /* Decode a number */
  135. static long
  136. decode(bpp)
  137. struct mbuf **bpp;
  138. {
  139.     register int x;
  140.  
  141.     x = PULLCHAR(bpp);
  142.     if(x == 0){
  143.         return pull16(bpp);    /* pull16 returns -1 on error */
  144.     } else {
  145.         return (long)x;        /* -1 if PULLCHAR returned error */
  146.     }
  147. }
  148.  
  149. int
  150. slhc_compress(comp, bpp, compress_cid)
  151. struct slcompress *comp;
  152. struct mbuf **bpp;
  153. int compress_cid;
  154. {
  155.     register struct cstate *ocs = &(comp->tstate[comp->xmit_oldest]);
  156.     register struct cstate *lcs = ocs;
  157.     register struct cstate *cs = lcs->next;
  158.     register int16 hlen;
  159.     register struct tcp *oth;
  160.     register unsigned long deltaS, deltaA;
  161.     register int16 changes = 0;
  162.     char new_seq[16];
  163.     register char *cp = new_seq;
  164.     struct mbuf *bp;
  165.     struct tcp th;
  166.     struct ip iph;
  167.  
  168.     /* Extract IP header */
  169.     hlen = ntohip(&iph,bpp);
  170.  
  171.     /* Bail if this packet isn't TCP, or is an IP fragment */
  172.     if(iph.protocol != TCP_PTCL || iph.offset != 0 || iph.flags.mf){
  173.         /* Send as regular IP */
  174.         if(iph.protocol != TCP_PTCL)
  175.             comp->sls_o_nontcp++;
  176.         else
  177.             comp->sls_o_tcp++;
  178.         *bpp = htonip(&iph,*bpp,IP_CS_OLD);
  179.         return SL_TYPE_IP;
  180.     }
  181.     /* Extract TCP header */
  182.     hlen += ntohtcp(&th,bpp);
  183.  
  184.     /*  Bail if the TCP packet isn't `compressible' (i.e., ACK isn't set or
  185.      *  some other control bit is set).
  186.      */
  187.     if(th.flags.syn || th.flags.fin || th.flags.rst || !th.flags.ack){
  188.         /* TCP connection stuff; send as regular IP */
  189.         comp->sls_o_tcp++;
  190.         *bpp = htontcp(&th,*bpp,NULLHEADER);
  191.         *bpp = htonip(&iph,*bpp,IP_CS_OLD);
  192.         return SL_TYPE_IP;
  193.     }
  194.     /*
  195.      * Packet is compressible -- we're going to send either a
  196.      * COMPRESSED_TCP or UNCOMPRESSED_TCP packet.  Either way,
  197.      * we need to locate (or create) the connection state.
  198.      *
  199.      * States are kept in a circularly linked list with
  200.      * xmit_oldest pointing to the end of the list.  The
  201.      * list is kept in lru order by moving a state to the
  202.      * head of the list whenever it is referenced.  Since
  203.      * the list is short and, empirically, the connection
  204.      * we want is almost always near the front, we locate
  205.      * states via linear search.  If we don't find a state
  206.      * for the datagram, the oldest state is (re-)used.
  207.      */
  208.     for ( ; ; ) {
  209.         if( iph.source == cs->cs_ip.source
  210.          && iph.dest == cs->cs_ip.dest
  211.          && th.source == cs->cs_tcp.source
  212.          && th.dest == cs->cs_tcp.dest)
  213.             goto found;
  214.  
  215.         /* if current equal oldest, at end of list */
  216.         if ( cs == ocs )
  217.             break;
  218.         lcs = cs;
  219.         cs = cs->next;
  220.         comp->sls_o_searches++;
  221.     };
  222.     /*
  223.      * Didn't find it -- re-use oldest cstate.  Send an
  224.      * uncompressed packet that tells the other side what
  225.      * connection number we're using for this conversation.
  226.      *
  227.      * Note that since the state list is circular, the oldest
  228.      * state points to the newest and we only need to set
  229.      * xmit_oldest to update the lru linkage.
  230.      */
  231.     comp->sls_o_misses++;
  232.     comp->xmit_oldest = lcs->this;
  233.  
  234.     goto uncompressed;
  235.  
  236. found:
  237.     /*
  238.      * Found it -- move to the front on the connection list.
  239.      */
  240.     if(lcs == ocs) {
  241.         /* found at most recently used */
  242.     } else if (cs == ocs) {
  243.         /* found at least recently used */
  244.         comp->xmit_oldest = lcs->this;
  245.     } else {
  246.         /* more than 2 elements */
  247.         lcs->next = cs->next;
  248.         cs->next = ocs->next;
  249.         ocs->next = cs;
  250.     }
  251.  
  252.     /*
  253.      * Make sure that only what we expect to change changed.
  254.      * Check the following:
  255.      * IP protocol version, header length & type of service.
  256.      * The "Don't fragment" bit.
  257.      * The time-to-live field.
  258.      * The TCP header length.
  259.      * IP options, if any.
  260.      * TCP options, if any.
  261.      * If any of these things are different between the previous &
  262.      * current datagram, we send the current datagram `uncompressed'.
  263.      */
  264.     oth = &cs->cs_tcp;
  265.  
  266.     if(iph.version != cs->cs_ip.version || iph.optlen != cs->cs_ip.optlen
  267.      || iph.tos != cs->cs_ip.tos
  268.      || iph.flags.df != cs->cs_ip.flags.df
  269.      || iph.ttl != cs->cs_ip.ttl
  270.      || th.optlen != cs->cs_tcp.optlen
  271.      || (iph.optlen > 0 && memcmp(iph.options,cs->cs_ip.options,iph.optlen) != 0)
  272.      || (th.optlen > 0 && memcmp(th.options,cs->cs_tcp.options,th.optlen) != 0)){
  273.         goto uncompressed;
  274.     }
  275.     /*
  276.      * Figure out which of the changing fields changed.  The
  277.      * receiver expects changes in the order: urgent, window,
  278.      * ack, seq (the order minimizes the number of temporaries
  279.      * needed in this section of code).
  280.      */
  281.     if(th.flags.urg){
  282.         deltaS = th.up;
  283.         cp = encode(cp,deltaS);
  284.         changes |= NEW_U;
  285.     } else if(th.up != oth->up){
  286.         /* argh! URG not set but urp changed -- a sensible
  287.          * implementation should never do this but RFC793
  288.          * doesn't prohibit the change so we have to deal
  289.          * with it. */
  290.         goto uncompressed;
  291.     }
  292.     if((deltaS = th.wnd - oth->wnd) != 0){
  293.         cp = encode(cp,deltaS);
  294.         changes |= NEW_W;
  295.     }
  296.     if((deltaA = th.ack - oth->ack) != 0L){
  297.         if(deltaA > 0x0000ffff)
  298.             goto uncompressed;
  299.         cp = encode(cp,deltaA);
  300.         changes |= NEW_A;
  301.     }
  302.     if((deltaS = th.seq - oth->seq) != 0L){
  303.         if(deltaS > 0x0000ffff)
  304.             goto uncompressed;
  305.         cp = encode(cp,deltaS);
  306.         changes |= NEW_S;
  307.     }
  308.  
  309.     switch(changes){
  310.     case 0:    /* Nothing changed. If this packet contains data and the
  311.          * last one didn't, this is probably a data packet following
  312.          * an ack (normal on an interactive connection) and we send
  313.          * it compressed.  Otherwise it's probably a retransmit,
  314.          * retransmitted ack or window probe.  Send it uncompressed
  315.          * in case the other side missed the compressed version.
  316.          */
  317.         if(iph.length != cs->cs_ip.length && cs->cs_ip.length == hlen)
  318.             break;
  319.         goto uncompressed;
  320.     case SPECIAL_I:
  321.     case SPECIAL_D:
  322.         /* actual changes match one of our special case encodings --
  323.          * send packet uncompressed.
  324.          */
  325.         goto uncompressed;
  326.     case NEW_S|NEW_A:
  327.         if(deltaS == deltaA &&
  328.             deltaS == cs->cs_ip.length - hlen){
  329.             /* special case for echoed terminal traffic */
  330.             changes = SPECIAL_I;
  331.             cp = new_seq;
  332.         }
  333.         break;
  334.     case NEW_S:
  335.         if(deltaS == cs->cs_ip.length - hlen){
  336.             /* special case for data xfer */
  337.             changes = SPECIAL_D;
  338.             cp = new_seq;
  339.         }
  340.         break;
  341.     }
  342.     deltaS = iph.id - cs->cs_ip.id;
  343.     if(deltaS != 1){
  344.         cp = encode(cp,deltaS);
  345.         changes |= NEW_I;
  346.     }
  347.     if(th.flags.psh)
  348.         changes |= TCP_PUSH_BIT;
  349.     /* Grab the cksum before we overwrite it below.  Then update our
  350.      * state with this packet's header.
  351.      */
  352.     deltaA = th.checksum;
  353.     ASSIGN(cs->cs_ip,iph);
  354.     ASSIGN(cs->cs_tcp,th);
  355.     /* We want to use the original packet as our compressed packet.
  356.      * (cp - new_seq) is the number of bytes we need for compressed
  357.      * sequence numbers.  In addition we need one byte for the change
  358.      * mask, one for the connection id and two for the tcp checksum.
  359.      * So, (cp - new_seq) + 4 bytes of header are needed.
  360.      */
  361.     deltaS = cp - new_seq;
  362.     if(compress_cid == 0 || comp->xmit_current != cs->this){
  363.         bp = *bpp = pushdown(*bpp,deltaS + 4);
  364.         cp = bp->data;
  365.         *cp++ = changes | NEW_C;
  366.         *cp++ = cs->this;
  367.         comp->xmit_current = cs->this;
  368.     } else {
  369.         bp = *bpp = pushdown(*bpp,deltaS + 3);
  370.         cp = bp->data;
  371.         *cp++ = changes;
  372.     }
  373.     cp = put16(cp,(int16)deltaA);    /* Write TCP checksum */
  374.     memcpy(cp,new_seq,deltaS);    /* Write list of deltas */
  375.     comp->sls_o_compressed++;
  376.     return SL_TYPE_COMPRESSED_TCP;
  377.  
  378.     /* Update connection state cs & send uncompressed packet (i.e.,
  379.      * a regular ip/tcp packet but with the 'conversation id' we hope
  380.      * to use on future compressed packets in the protocol field).
  381.      */
  382. uncompressed:
  383.     iph.protocol = cs->this;
  384.     ASSIGN(cs->cs_ip,iph);
  385.     ASSIGN(cs->cs_tcp,th);
  386.     comp->xmit_current = cs->this;
  387.     comp->sls_o_uncompressed++;
  388.     *bpp = htontcp(&th,*bpp,NULLHEADER);
  389.     *bpp = htonip(&iph,*bpp,IP_CS_OLD);
  390.     return SL_TYPE_UNCOMPRESSED_TCP;
  391. }
  392.  
  393.  
  394. int
  395. slhc_uncompress(comp, bpp)
  396. struct slcompress *comp;
  397. struct mbuf **bpp;
  398. {
  399.     register int changes;
  400.     long x;
  401.     register struct tcp *thp;
  402.     register struct cstate *cs;
  403.     int len;
  404.  
  405.     /* We've got a compressed packet; read the change byte */
  406.     comp->sls_i_compressed++;
  407.     if(len_p(*bpp) < 3){
  408.         comp->sls_i_error++;
  409.         return 0;
  410.     }
  411.     changes = PULLCHAR(bpp);    /* "Can't fail" */
  412.     if(changes & NEW_C){
  413.         /* Make sure the state index is in range, then grab the state.
  414.          * If we have a good state index, clear the 'discard' flag.
  415.          */
  416.         x = PULLCHAR(bpp);    /* Read conn index */
  417.         if(x < 0 || x > comp->rslot_limit)
  418.             goto bad;
  419.  
  420.         comp->flags &=~ SLF_TOSS;
  421.         comp->recv_current = x;
  422.     } else {
  423.         /* this packet has an implicit state index.  If we've
  424.          * had a line error since the last time we got an
  425.          * explicit state index, we have to toss the packet. */
  426.         if(comp->flags & SLF_TOSS){
  427.             comp->sls_i_tossed++;
  428.             return 0;
  429.         }
  430.     }
  431.     cs = &comp->rstate[comp->recv_current];
  432.     thp = &cs->cs_tcp;
  433.  
  434.     if((x = pull16(bpp)) == -1)    /* Read the TCP checksum */
  435.         goto bad;
  436.     thp->checksum = x;
  437.  
  438.     thp->flags.psh = (changes & TCP_PUSH_BIT) ? 1 : 0;
  439.  
  440.     switch(changes & SPECIALS_MASK){
  441.     case SPECIAL_I:        /* Echoed terminal traffic */
  442.         {
  443.         register int16 i;
  444.         i = cs->cs_ip.length;
  445.         i -= (cs->cs_ip.optlen + IPLEN + TCPLEN);
  446.         thp->ack += i;
  447.         thp->seq += i;
  448.         }
  449.         break;
  450.  
  451.     case SPECIAL_D:            /* Unidirectional data */
  452.         thp->seq += cs->cs_ip.length - (cs->cs_ip.optlen +IPLEN + TCPLEN);
  453.         break;
  454.  
  455.     default:
  456.         if(changes & NEW_U){
  457.             thp->flags.urg = 1;
  458.             if((x = decode(bpp)) == -1)
  459.                 goto bad;
  460.             thp->up = x;
  461.         } else
  462.             thp->flags.urg = 0;
  463.         if(changes & NEW_W){
  464.             if((x = decode(bpp)) == -1)
  465.                 goto bad;
  466.             thp->wnd += x;
  467.         }
  468.         if(changes & NEW_A){
  469.             if((x = decode(bpp)) == -1)
  470.                 goto bad;
  471.             thp->ack += x;
  472.         }
  473.         if(changes & NEW_S){
  474.             if((x = decode(bpp)) == -1)
  475.                 goto bad;
  476.             thp->seq += x;
  477.         }
  478.         break;
  479.     }
  480.     if(changes & NEW_I){
  481.         if((x = decode(bpp)) == -1)
  482.             goto bad;
  483.         cs->cs_ip.id += x;
  484.     } else
  485.         cs->cs_ip.id++;
  486.  
  487.     /*
  488.      * At this point, bpp points to the first byte of data in the
  489.      * packet.  Put the reconstructed TCP and IP headers back on the
  490.      * packet.  Recalculate IP checksum (but not TCP checksum).
  491.      */
  492.     len = len_p(*bpp) + IPLEN + TCPLEN + cs->cs_ip.optlen;
  493.     cs->cs_ip.length = len;
  494.  
  495.     *bpp = htontcp(thp,*bpp,NULLHEADER);
  496.     *bpp = htonip(&cs->cs_ip,*bpp,IP_CS_NEW);
  497.     return len;
  498. bad:
  499.     comp->sls_i_error++;
  500.     return slhc_toss( comp );
  501. }
  502.  
  503.  
  504. int
  505. slhc_remember(comp, bpp)
  506. struct slcompress *comp;
  507. struct mbuf **bpp;
  508. {
  509.     register struct cstate *cs;
  510.     struct ip iph;
  511.     struct tcp th;
  512.  
  513.     /* Extract IP and TCP headers and verify conn ID */
  514.     ntohip(&iph,bpp);
  515.     ntohtcp(&th,bpp);
  516.     if(uchar(iph.protocol) > comp->rslot_limit) {
  517.         comp->sls_i_error++;
  518.         return slhc_toss(comp);
  519.     }
  520.  
  521.     /* Update local state */
  522.     cs = &comp->rstate[comp->recv_current = uchar(iph.protocol)];
  523.     comp->flags &=~ SLF_TOSS;
  524.     iph.protocol = TCP_PTCL;
  525.     ASSIGN(cs->cs_ip,iph);
  526.     ASSIGN(cs->cs_tcp,th);
  527.  
  528.     /* Put headers back on packet
  529.      * Neither header checksum is recalculated
  530.      */
  531.     *bpp = htontcp(&th,*bpp,NULLHEADER);
  532.     *bpp = htonip(&iph,*bpp,IP_CS_OLD);
  533.     comp->sls_i_uncompressed++;
  534.     return len_p(*bpp);
  535. }
  536.  
  537.  
  538. int
  539. slhc_toss(comp)
  540. struct slcompress *comp;
  541. {
  542.     if ( comp == NULLSLCOMPR )
  543.         return 0;
  544.  
  545.     comp->flags |= SLF_TOSS;
  546.     return 0;
  547. }
  548.  
  549. void
  550. slhc_i_status(comp)
  551. struct slcompress *comp;
  552. {
  553.     if (comp != NULLSLCOMPR) {
  554.         printf("\t%10ld Cmp,"
  555.             " %10ld Uncmp,"
  556.             " %10ld Bad, "
  557.             " %10ld Tossed\n",
  558.             comp->sls_i_compressed,
  559.             comp->sls_i_uncompressed,
  560.             comp->sls_i_error,
  561.             comp->sls_i_tossed);
  562.     }
  563. }
  564.  
  565.  
  566. void
  567. slhc_o_status(comp)
  568. struct slcompress *comp;
  569. {
  570.     if (comp != NULLSLCOMPR) {
  571.         printf("\t%10ld Cmp,"
  572.             " %10ld Uncmp,"
  573.             " %10ld AsIs,"
  574.             " %10ld NotTCP\n",
  575.             comp->sls_o_compressed,
  576.             comp->sls_o_uncompressed,
  577.             comp->sls_o_tcp,
  578.             comp->sls_o_nontcp);
  579.         printf("\t%10ld Searches,"
  580.             " %10ld Misses\n",
  581.             comp->sls_o_searches,
  582.             comp->sls_o_misses);
  583.     }
  584. }
  585.  
  586.  
  587.